
/*
* Copyright (c) 2013 City University of Hongkong.
*                    Cloud computing security group.
* 
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
* 
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
* 
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/

/*
* graph.h - Graph base class.
*
* Authors: Xingliang Yuan     
* Emails:  xyuan86@gmail.com
*
*/

#ifndef GRAPH_H
#define GRAPH_H

#include "../version.h"

struct edge
{
    unsigned int in; 
    unsigned int out;
    float delay;
    int c_tag; //mark the criticality for identifying the critical path
}; // edge struct (in, out, delay)

class graph
{
protected:
    unsigned int vertex_num;        // total vertex number
    unsigned int edge_num;          // total edge number

    //std::vector<unsigned int> vertex_set; 

    //vertex color: 0 white; 1 gray; 2 black
    vector<unsigned int> vertex_color;

    vector <unsigned int> tp_idx; //vertex's real order

    /*  
    * description: DFS_visit subroutine in topological sort
    * param: current visit vertex
    * return: 
    */
    void tp_visit(const unsigned int &vertex);

    /*  
    * description: relabeling edge src and dist by tp_order
    * param: 
    * return: 
    */
    void edge_tp_label(); 

public:
    //graph () {};  //uncomment to implement constructor

    // vertex sorted by topological order
    vector<unsigned int> tp_order;

    //variable-length vertex adjacent list, fast graph topology update
    vector< vector<edge> >vertex_fanin; 
    vector< vector<edge> >vertex_fanout;

    vector<edge> edge_set;   // edge set

    /*  
    * description: fanins,fanouts by re-ordering edges, start with v_0, v_1, ...
    * param: address of fanins, fanouts
    * return: 
    */
    void gen_fanins();
    void gen_fanouts();

    /*  
    * description: topological sort graph
    * param: 
    * return: 
    */
    void tp_sort(); 

    /*  
    * description: get total vertex number
    * param: null
    * return: vertex_num
    */
    unsigned int get_vertex_num() {
        return vertex_num;
    };

    /*  
    * description: get total edge number
    * param: null
    * return: edge_num
    */
    unsigned int get_edge_num() {
        return edge_num;
    };

    /*  
    * description: set vertex number
    * param: 
    * return: 
    */
    void set_vertex_num(unsigned int n) {
        vertex_num = n;
    };

    /*  
    * description: set edge number
    * param: 
    * return: 
    */
    void set_edge_num(unsigned int n) {
        edge_num = n;
    };

    /*  
    * description: get edge i
    * param: edge index
    * return: edge i
    */
    struct edge get_edge(unsigned int edge_index) {
        return edge_set[edge_index];
    };

    /*  
    * description: get vertex color
    * param: vertex index
    * return: vertex color
    */
    unsigned int get_vertex_color(unsigned int vertex_index) {
        return vertex_color[vertex_index];
    };

    /*  
    * description: set vertex color
    * param: vertex index
    * return: 
    */
    void set_vertex_color(unsigned int vertex_index, unsigned int color) {
        //assert(0<= color && color <= 2);
        vertex_color[vertex_index] = color;
    };

    /*  
    * description: initial vertex color by white
    * param:
    * return: 
    */
    void initial_vertex_color() {
        vertex_color.assign(vertex_num, 0);
    };

}; // graph class

#endif // GRAPH_H
